﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace StrategyAndSort
{
    class HalfInsertSort:ISortStrategy
    {
        public void Sort<T>(IList<T> array,int keyNm =0) where T : IComparable
        {
            int low, high, mid;
            for(int i = 1; i < array.Count; i++)
            {
                T temp = array[i];
                low = 0;high = i - 1;
                //折半查找插入位置
                while (low <= high)
                {
                    mid=(low + high) / 2;
                    if (array[mid].CompareTo(temp) > 0) high = mid - 1;
                    else if (array[mid].Equals(temp))  { low = mid + 1; break; }
                    else low = mid + 1;
                }
                for (int j = i; j >low; j--) array[j] = array[j-1];
                array[low] = temp;
            }
        }
    }
}
